This invention relates in general to the field of computer graphics and more particularly to the field of simplification of geometrical representations of objects.
Geometric models, usually represented by a collection of triangles, are becoming increasingly complex, as acquisition systems improve. The performance of interactive environments using or displaying the data can be improved by reducing the size of the data. This data size reduction is the objective of surface simplification techniques. Such techniques accept surfaces as input and return arbitrarily simplified surfaces as output.
One data modeling technique is modeling three-dimensional surfaces as height fields. In a height field a two-dimensional grid has a corresponding value in a third dimension, i.e., for each (x,y) coordinate there is a corresponding height, z. Height field data is an important geometric representation in many fields, such as geoscience.
One problem is how to simplify height field data which contains missing values, in particular, how to generate topologically correct continuous level of detail (LOD) approximations efficiently. A topologically correct simplification is one that does not have self-intersections of boundaries in parameter space in any approximation and also preserves the genus of the surface. A configuration demonstrating a self-intersecting simplification is shown in FIG. 2. The standard simplification operators presented in the literature cannot handle the self-intersection problem well, and consequently they cannot guarantee intersection-free approximation in image space. This problem has previously been attacked using two different strategies:
I. Explicitly checking whether a simplification operation introduces self-intersections (O. G. Staadt and M. H. Gross, xe2x80x9cProgressive tetrahedralizations,xe2x80x9d Proceedings IEEE Visualization ""98, pp. 397-402, IEEE, 1998.). However, these check operations are global in nature, and although they can be accelerated, slow the simplification algorithms down.
II. Detecting self-intersections using local operations by triangulating the holes present in the surface. Depending on the simplification operator used, a self-intersection can be detected by analyzing the neighbor triangles defined over the hole. For example, if the vertex xij of FIG. 2a was to be removed using an edge collapse operation (described in greater detail below and in H. Hoppe, xe2x80x9cProgressive meshes,xe2x80x9d In H. Rushmeier, editor, SIGGRAPH 96 Conference Proceedings, Annual Conference Series, pages 99-108, ACM SIGGRAPH, Addison Wesley, August 1996.) onto the vertex xk,l, the self-inter-section that would be introduced could be detected by noting that the gray triangle 201 flipped as illustrated by the triangles 201xe2x80x2 and 201xe2x80x3 of FIG. 2b during the operation.
Surface simplification is an important core technology in many applications, and as a consequence many different research groups have focused on creating flexible and efficient frameworks to handle large data sets. One approach is introduced in W. J. Schrxc3x6der, J. A. Zarge, and W. E. Lorensen. xe2x80x9cDecimation of triangle meshes.xe2x80x9d In E. E. Catmull, editor, ComputerGraphics (SIGGRAPH ""92 Proceedings), volume 26, pages 65-70, July 1992 and further described in U.S. Pat. No. 5,590,248, to Jonathan A. Zarge and William J. Schroeder, xe2x80x9cMethod for Reducing the Complexity of a Polygonal Mesh, filed Feb. 24, 1995, continuation of Ser. No. 815,772, Jan. 2, 1992, abandoned. In that article, the authors introduced the fundamental vertex removal operator. Using this operator, surfaces are simplified by removing one vertex at a time, and then re-triangulating the hole introduced by removal operation. This operator, in conjunction with a divide and conquer triangulation strategy, is powerful enough to handle complex surfaces, such as general two-manifolds. The operator was subsequently used as one approach to construct multiresolution representations of height field data.
The second fundamental operator of edge collapse was introduced in H. Hoppe. xe2x80x9cProgressive meshes.xe2x80x9d In H. Rushmeier, editor, SIGGRAPH 96 Conference Proceedings, Annual Conference Series, pages 99-108. ACM SIGGRAPH, Addison Wesley, August 1996, held in New Orleans, La., Aug. 04-09, 1996. This technique is also described in U.S. Pat. No. 5,929,860 to Hoppe; Hugues H., entitled xe2x80x9cMesh simplification and construction of progressive meshes,xe2x80x9d filed Feb. 7, 1997, continuation of Ser. No. 08/586,953, filed Jan. 11, 1996.
The edge-collapse operator simplifies meshes by collapsing the pair of vertices joined by an edge. The advantage of this approach is that there is no need to re-triangulate holes as in the case of vertex removal algorithms. On the downside, meshes generated by this approach might have poor characteristics, unless the set of allowable edge collapses are chosen carefully.
While the previous operators are generally applicable to two-manifold surfaces, much effort has been spent in constructing representations for height field data stored in regular grids. In M. H. Gross, O. G. Staadt, and R. Gatti. xe2x80x9cEfficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures.xe2x80x9d IEEE Transactions on Visualization and Computer Graphics, 2(2):130-143, June 1996, the authors used a wavelets representation of height fields coupled with a look-up table to construct multi-resolution approximations of data defined on a regular domain. In R. Pajarola. xe2x80x9cLarge scale terrain visualization using the restricted quadtree triangulation.xe2x80x9d In Proceedings IEEE Visualization""98, pages 19-26. IEEE, 1998, a quadtree was used to store the data. By restricting the choice of the vertices present in any approximation, Pajarola could define a look-up table that not only could triangulate the chosen vertices, but could also generate a single triangle strip. Both of these approaches have the advantage of being fast, since they are optimized for height field data, but they have the disadvantage that they work best with grids whose size is a power of two. If this is not the case, then it is necessary to extend the basic algorithms to handle many different special cases. For the same reason, it would be extremely difficult to let these structures handle height fields with missing values.
All of the representations discussed in this section are capable of guaranteeing that a simplification operation will not change the topology of the surface locally. However, none of them is capable of guaranteeing that a simplification operation will not introduce a self-intersection. With avoidance of self-intersection as a requirement, one of the two approaches described above would need to be implemented.
For these reasons there is an unmet need for an efficient surface simplification method that accepts a height field as input and that produces a topologically correct surface simplification.